package com.zhn;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 */

public class Subsets {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>());
        traceBacking(nums,0);
        return res;
    }

    //回溯算法
    public void traceBacking(int[] num,int startIndex){
        if(startIndex >= num.length)
            return;
        for(int i = startIndex; i < num.length; i++){
            path.add(num[i]);
            res.add(new ArrayList<>(path));
            traceBacking(num,i+1);
//            //回溯
//            path.remove(path.size() - 1);
        }
    }
}
class Test{
    public static void main(String[] args) {
        Subsets subsets = new Subsets();
        List<List<Integer>> subsets1 = subsets.subsets(new int[]{1, 2, 3});
        System.out.println(subsets1);
    }
}
